Tháng 10 năm 1997, sau khi tốt nghiệp đại học, Mai Văn Hải trở lại Thanh Hóa, được tuyển dụng công chức vào Ủy ban nhân dân tỉnh Thanh Hóa, điều về huyện Nga Sơn làm cán bộ Thanh tra Ủy ban nhân dân huyện Nga Sơn. Tháng 11 năm 2005, ông được bầu làm Ủy viên Ban Chấp hành Đảng bộ huyện, được bổ nhiệm làm Chánh Thanh tra Ủy ban nhân dân huyện vào tháng 11 năm 2006. Vào tháng 12 năm 2009, ông được bầu vào Ban Thường vụ Huyện ủy, nhậm chức Chủ nhiệm Ủy ban Kiểm tra Huyện ủy Nga Sơn, sau đó 1 năm vào tháng 8 năm 2010 thì được phân công làm Phó Bí thư thường trực Huyện ủy, và trúng cử Đại biểu Hội đồng nhân dân huyện Nga Sơn. Tháng 10 năm 2014, ông được bầu làm Bí thư Huyện ủy,[3] Chủ tịch Hội đồng nhân dân huyện, Bí thư Đảng ủy Quân sự huyện Nga Sơn, sau đó được bầu vào Ban Chấp hành Đảng bộ tỉnh Thanh Hóa từ tháng 12 năm này, đồng thời tái đắc cử Tỉnh ủy viên tại Đại hội Đảng bộ tỉnh lần thứ XVIII, nhiệm kỳ 2015–2020.[4] Trong giai đoạn này, ông cũng là Đại biểu Hội đồng nhân dân tỉnh Thanh Hóa khóa XVII, nhiệm kỳ 2016–2021.[5]

Tháng 9 năm 2020, Mai Văn Hải tiếp tục được bầu làm Tỉnh ủy viên tại Đại hội Đảng bộ tỉnh lần thứ XIX, nhiệm kỳ 2020–2025,[6] được điều lên tỉnh, nhậm chức Phó Bí thư Đảng ủy Khối Cơ quan và Doanh nghiệp tỉnh. Năm 2021, ông được Ủy ban Trung ương Mặt trận Tổ quốc Việt Nam tỉnh giới thiệu tham gia ứng cử đại biểu quốc hội từ Thanh Hóa,[7] bầu cử ở đơn vị bầu cử số 2 gồm thị xã Bỉm Sơn, huyện Hà Trung, Nga Sơn, Hậu Lộc, Vĩnh Lộc, Thạch Thành,[8] rồi trúng cử Đại biểu Quốc hội khóa XV với tỷ lệ 93,94%.[9][10] Ngày 21 tháng 7 năm 2021, ông được phê chuẩn làm Ủy viên Ủy ban Kinh tế của Quốc hội và Phó Trưởng Đoàn Đại biểu Quốc hội tỉnh Thanh Hóa.[11]